翻訳と辞書 Words near each other ・ Feral boar ・ Feral Brewing Company ・ Fenwick Island State Park ・ Fenwick Island, Delaware ・ Fenwick Lansdowne ・ Fenwick Lawson ・ Fenwick Lionel Kelly ・ Fenwick Pier ・ Fenwick Settlement, Missouri ・ Fenwick Skrimshire ・ Fenwick Smith ・ Fenwick Tower ・ Fenwick Tower (Halifax) ・ Fenwick Tower (Northumberland) ・ Fenwick Travers ・ Fenwick tree ・ Fenwick W. English ・ Fenwick Weavers' Society ・ Fenwick Williams ・ Fenwick, Connecticut ・ Fenwick, East Ayrshire ・ Fenwick, Nova Scotia ・ Fenwick, Ontario ・ Fenwick, South Yorkshire ・ Fenwick, West Virginia ・ Fenwick2 Health and Wellbeing Centre ・ Fenwicke Holmes ・ Fenwicks Scrub Flora Reserve ・ Fenwood Road (MBTA station) ・ Fenwood, Saskatchewan Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fenwick tree ： ウィキペディア英語版 Fenwick tree A Fenwick tree or binary indexed tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values. It was proposed by Peter Fenwick in 1994. Fenwick trees primarily solve the problem of balancing prefix sum calculation efficiency with element modification efficiency. The efficiency of these operations comes as a trade-off - greater efficiency in prefix sum calculation is achieved by pre-calculating values, but as more values are pre-calculated more must be re-calculated upon any modification to the underlying value table. Fenwick trees both calculate prefix sums and modify the table in $O(\backslash log\; n)$ time, where $n$ is the size of the table. ==Description== Given a table of elements, it is sometimes desirable to calculate the running total of values up to each index according to some associative binary operation (addition on integers, for example). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value table and having all further queries reflect those changes. Although Fenwick trees are trees in concept, in practice they are implemented using a flat array analogous to implementations of a binary heap. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each index contains the pre-calculated sum of a section of the table, and by combining that sum with section sums encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all section sums which contain the modified value are in turn modified during a similar traversal of the tree. The section sums are defined in such a way that queries and modifications to the table are executed in asymptotically equivalent time - $O(\backslash log\; n)$ in the worst case. The initial process of building the Fenwick tree over a table of values runs in $O(n\; \backslash log\; n)$ time. Other efficient operations include locating the index of a value if all values are positive, or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in $O(n)$ time. The sum of an arbitrary subarray can also be calculated by subtracting the prefix sum before its start point from the prefix sum at its end point. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fenwick tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.